package com.fang.sort;

import java.util.Comparator;

import com.fang.base.utils.SwapUtils;

/**
 * <pre>
 * 算法描述

堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得在当前无序区中选取最大（或最小）关键字的记录变得简单。 
（1）用大根堆排序的基本思想 
① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区 
② 再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key 
③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。 
…… 
直到无序区只有一个元素为止。 
（2）大根堆排序算法的基本操作： 
①建堆，建堆是不断调整堆的过程，从len/2处开始调整，一直到第一个节点，此处len是堆中元素的个数。建堆的过程是线性的过程，从len/2到0处一直调用调整堆的过程，相当于o(h1)+o(h2)…+o(hlen/2) 其中h表示节点的深度，len/2表示节点的个数，这是一个求和的过程，结果是线性的O(n)。 
②调整堆：调整堆在构建堆的过程中会用到，而且在堆排序过程中也会用到。利用的思想是比较节点i和它的孩子节点left(i),right(i)，选出三者最大(或者最小)者，如果最大（小）值不是节点i而是它的一个孩子节点，那边交互节点i和该节点，然后再调用调整堆过程，这是一个递归的过程。调整堆的过程时间复杂度与堆的深度有关系，是lgn的操作，因为是沿着深度方向进行调整的。 
③堆排序：堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)，将前面len-1个节点继续进行堆调整的过程，然后再将根节点取出，这样一直到所有节点都取出。堆排序过程的时间复杂度是O(nlgn)。因为建堆的时间复杂度是O(n)（调用一次）；调整堆的时间复杂度是lgn，调用了n-1次，所以堆排序的时间复杂度是O(nlgn)[2]
 * </pre>
 * 
 */
public class HeapSort {

	public static void main(String[] args) {
		Integer[] sort = { 2, 5, 45, 87, 1, 254, 58 };

		Integer[] data = HeapSort.sort(sort, new Comparator<Integer>() {
			@Override
			public int compare(Integer data1, Integer data2) {
				if (data1 < data2)
					return 1;
				if (data1 > data2)
					return -1;
				return 0;
			}
		});
		for (Integer integer : data) {
			System.out.print(integer + "   ");
		}
	}

	public static <T> T[] sort(T[] data, Comparator<? super T> comparator) {
		if (data == null || comparator == null)
			return data;
		// 这是建堆的过程，一次从倒数第二层的根节点开始调整堆，即数组下标为i/2开始，一直到顶层根节点，这样就建好堆了。。
		int mid = (data.length - 1) >> 1;
		for (int i = mid; i >= 0; i--) {
			adjust(data, i, data.length - 1, comparator);
		}

		// 末尾与头交换，交换后调整最大堆
		for (int i = data.length - 1; i > 0; i--) {
			SwapUtils.swap(data, 0, i);
			adjust(data, 0, i - 1, comparator);
		}

		return data;
	}

	/**
	 * 
	 * @param data
	 *            要调整的数组，即堆
	 * @param rootIndex
	 *            调整的根节点，即起始位置
	 * @param maxIndex
	 *            要调整的终止位置
	 * @param comparator
	 */
	private static <T> void adjust(T[] data, int rootIndex, int maxIndex, Comparator<? super T> comparator) {
		T rootData = data[rootIndex];

		// 左孩子
		int maxChildIndex = (rootIndex << 1) + 1;

		// 调整rootData的位置.注意这里的判断条件（左孩子的最大值是当前最大位置）
		while (maxChildIndex <= maxIndex) {
			// 比较左右孩子，如果右孩子大，则把maxChildIndex的值改为右孩子
			// 比较左右孩子，取出较大的孩子
			// 由于下面的代码涉及到右孩子，所以左孩子必须得小于最大位置-1
			if ((maxChildIndex < maxIndex) && (comparator.compare(data[maxChildIndex], data[maxChildIndex + 1]) > 0)) {
				maxChildIndex = maxChildIndex + 1;
			}
			// 如果根节点大于孩子节点则退出循环，不用调整
			if (comparator.compare(data[maxChildIndex], rootData) > 0) {
				break;
			}
			// 较大的孩子节点值赋值给根节点
			data[(maxChildIndex - 1) >> 1] = data[maxChildIndex];

			// 继续寻找左孩子
			maxChildIndex = (maxChildIndex << 1) + 1;
		}
		// 将根节点赋值给最后一个空出来的节点
		data[(maxChildIndex - 1) >> 1] = rootData;
	}

}
